#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <thread>
#include <atomic>
#include <memory>

#define LockFree
#ifndef LockFree
template <typename T>
class LockFreeStack
{
private:
	struct Node
	{
		T _data;
		Node* _next;

		Node(const T& val) :_data(val), _next(nullptr) {}
	};

	std::atomic<Node*> _head; // 原子头节点

public:
	// 禁止拷贝复制
	LockFreeStack() = default;
	LockFreeStack(const LockFreeStack&) = delete;
	LockFreeStack& operator=(const LockFreeStack&) = delete;

	~LockFreeStack()
	{
		while (pop());
	}

	void push(const T& val)
	{
		// 1.创建新节点
		Node* new_node = new Node(val);

		// 2.CAS循环：将新节点设置为头节点
		Node* old_head = _head.load(std::memory_order_acquire); // 获取语义，确保之后得读取操作不会重排到acquire之前

		// 多个线程同时压栈时，第一个进入循环的线程符合预期，修改完指针后，返回true退出循环
		// 第二个线程进入循环时，此时预期值与栈顶元素不相等，先将预期值改为当前值，然后进入循环内部，让新节点指向最新的头节点（在CAS操作时已经更新了）
		// 此时重新判断时，当前值与预期值相同，修改栈顶为newnode，返回true退出循环
		do {
			new_node->_next = old_head;
		} while (!_head.compare_exchange_weak(
			old_head,  // 预期栈顶元素
			new_node,  // 希望设置得新栈顶 
			std::memory_order_release,  // 成功时，释放语义，确保之前的写操作不能排在之后，目的让该线程的修改被其他线程看到
			std::memory_order_relaxed)); // 失败时，宽松语义
	}

	std::unique_ptr<T> pop()
	{
		Node* old_head = _head.load(std::memory_order_acquire);

		while (old_head != nullptr && !_head.compare_exchange_weak(
			old_head,
			old_head->_next,
			std::memory_order_acq_rel,
			std::memory_order_acquire // 失败时，获取语义，看到其他线程的修改
		))
			;// empty body

		// 此时old_head就是待pop的元素
		if (old_head == nullptr) return nullptr;

		std::unique_ptr<T> result = std::make_unique<T>(old_head->_data);
		delete old_head;
		return result;
	}

	bool empty() const
	{
		return _head.load(std::memory_order_acquire) == nullptr;
	}

	// 获取栈顶元素，不弹栈
	std::unique_ptr<T> peek() const
	{
		Node* current_head = _head.load(std::memory_order_acquire);
		if (current_head) {
			return std::make_unique<T>(current_head->_data);
		}
		return nullptr;
	}
};

void test_stack() {
    LockFreeStack<int> stack;

    std::cout << "=== 基本功能测试 ===" << std::endl;

    // 测试空栈 pop
    auto result = stack.pop();
    std::cout << "空栈pop: " << (result ? "有值" : "nullptr") << std::endl;

    // 测试 push 和 pop
    stack.push(1);
    stack.push(2);
    stack.push(3);

    std::cout << "压栈: 1, 2, 3" << std::endl;

    auto val3 = stack.pop();
    auto val2 = stack.pop();
    auto val1 = stack.pop();
    auto val0 = stack.pop();

    std::cout << "弹栈结果: ";
    if (val3) std::cout << *val3 << " ";
    if (val2) std::cout << *val2 << " ";
    if (val1) std::cout << *val1 << " ";
    if (!val0) std::cout << "nullptr";
    std::cout << std::endl;

    std::cout << "=== 多线程测试 ===" << std::endl;

    std::vector<std::thread> threads;
    const int num_threads = 4;
    const int operations = 10000;
    std::atomic<int> push_count{ 0 };
    std::atomic<int> pop_count{ 0 };

    // 生产者线程
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back([&stack, &push_count, i, operations]() {
            for (int j = 0; j < operations; ++j) {
                stack.push(i * operations + j);
                push_count.fetch_add(1, std::memory_order_relaxed);
            }
            });
    }

    // 消费者线程
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back([&stack, &pop_count, operations]() {
            for (int j = 0; j < operations; ++j) {
                if (auto item = stack.pop()) {
                    pop_count.fetch_add(1, std::memory_order_relaxed);
                }
            }
            });
    }

    for (auto& t : threads) {
        t.join();
    }

    std::cout << "Push操作: " << push_count.load() << std::endl;
    std::cout << "Pop操作: " << pop_count.load() << std::endl;
    std::cout << "栈是否为空: " << (stack.empty() ? "是" : "否") << std::endl;

    if (push_count == pop_count && stack.empty()) {
        std::cout << "测试通过!" << std::endl;
    }
    else {
        std::cout << "测试失败!" << std::endl;
    }
}

int main() 
{
    test_stack();
    return 0;
}
#endif



template <typename T>
class LockFreeStack
{
public:
	struct Node
	{
		T _data;
		Node* _next;

		Node(const T& val) :_data(val), _next(nullptr) {}
	};

	struct Top
	{
		Node* _ptr;       // 栈顶节点指针
		uint64_t _version; // 引入版本号，借助ABA问题

		Top(Node* ptr = nullptr, uint64_t v = 0) :_ptr(ptr), _version(v) {}

		// CAS默认只比较指针的值，而不比较指针的内容，导致地址重用，导致ABA问题
		// 引入版本号，CAS比较时，必须地址+版本号都相同，才算相同
		bool operator==(const Top& other) const
		{
			return _ptr == other._ptr && _version == other._version;
		}
	};

	std::atomic<Top> _head; // 原子头节点

public:
	// 禁止拷贝复制
	LockFreeStack() = default;
	LockFreeStack(const LockFreeStack&) = delete;
	LockFreeStack& operator=(const LockFreeStack&) = delete;

	~LockFreeStack()
	{
		while (pop());
	}

	void push(const T& val)
	{
		// 1.创建新节点
		Node* new_node = new Node(val);

		// 2.CAS循环：将新节点设置为头节点
		Top current = _head.load(std::memory_order_acquire); // 获取语义，确保之后得读取操作不会重排到acquire之前

		// 多个线程同时压栈时，第一个进入循环的线程符合预期，修改完指针后，返回true退出循环
		// 第二个线程进入循环时，此时预期值与栈顶元素不相等，先将预期值改为当前值，然后进入循环内部，让新节点指向最新的头节点（在CAS操作时已经更新了）
		// 此时重新判断时，当前值与预期值相同，修改栈顶为newnode，返回true退出循环
		do {
			new_node->_next = current._ptr;
		} while (!_head.compare_exchange_weak(
			current,  // 预期栈顶元素
			Top(new_node, current._version + 1),  // 希望设置得新栈顶，版本号加1
			std::memory_order_release,  // 成功时，释放语义，确保之前的写操作不能排在之后，目的让该线程的修改被其他线程看到
			std::memory_order_relaxed)); // 失败时，宽松语义
	}

	std::unique_ptr<T> pop()
	{
		Top current = _head.load(std::memory_order_acquire);

		while (current._ptr != nullptr && !_head.compare_exchange_weak(
			current,
			Top(current._ptr->_next, current._version + 1),
			std::memory_order_acq_rel,
			std::memory_order_acquire // 失败时，获取语义，看到其他线程的修改
		))
			;// empty body

		// 此时old_head就是待pop的元素
		if (current._ptr == nullptr) return nullptr;

		std::unique_ptr<T> result = std::make_unique<T>(current._ptr->_data);

		// 这里直接delete，会导致悬垂指针的问题
		// 两个线程同时持有该指针，但一个线程已经将该指针释放，另一个线程并不知道，再进行CAS操作时，就会导致对已释放的内存空间的访问，导致悬垂指针
		// 借助风险指针来避免悬垂指针的问题——TODO
		// 风险指针原理：
		// 每一个线程拥有一个风险指针数组，用来标记当前正在访问的节点
		// 当需要释放节点时，不直接delete，而是先放入全局的延迟回收队列
		// 定期遍历延迟回收队列，检查每个节点是否被任何线程的风险指针引用。若无人引用，则安全删除；否则继续保留 
		elete current._ptr;
		return result;
	}

	bool empty() const
	{
		return _head.load(std::memory_order_acquire)._ptr == nullptr;
	}

	// 获取栈顶元素，不弹栈
	std::unique_ptr<T> peek() const
	{
		Top current = _head.load(std::memory_order_acquire);
		if (current._ptr) {
			return std::make_unique<T>(current._ptr->_data);
		}
		return nullptr;
	}

	uint64_t get_version() const
	{
		return _head.load(std::memory_order_acquire)._version;
	}
};

void test_aba_safe_stack() {
    LockFreeStack<int> stack;

    std::cout << "=== ABA安全栈测试 ===" << std::endl;

    // 基本功能测试
    stack.push(1);
    stack.push(2);
    stack.push(3);

    std::cout << "当前版本: " << stack.get_version() << std::endl;

    auto val3 = stack.pop(); // 版本+1
    auto val2 = stack.pop(); // 版本+1  
    auto val1 = stack.pop(); // 版本+1
    auto val0 = stack.pop(); // 空栈

    std::cout << "最终版本: " << stack.get_version() << std::endl;

    // 多线程ABA场景测试
    std::cout << "\n=== 多线程ABA场景测试 ===" << std::endl;

    LockFreeStack<int> aba_test_stack;
    aba_test_stack.push(100);
    aba_test_stack.push(200);
    aba_test_stack.push(300);  // 栈: 300 → 200 → 100

    std::thread t1([&aba_test_stack]() {
        // 线程1：读取当前状态
        LockFreeStack<int>::Top current = aba_test_stack._head.load();
        std::cout << "线程1读取: ptr=" << current._ptr
            << ", version=" << current._version << std::endl;

        // 模拟被中断
        std::this_thread::sleep_for(std::chrono::milliseconds(100));

        // 尝试pop
        auto result = aba_test_stack.pop();
        if (result) {
            std::cout << "线程1弹出: " << *result << std::endl;
        }
        else {
            std::cout << "线程1弹出: 失败" << std::endl;
        }
        });

    std::thread t2([&aba_test_stack]() {
        std::this_thread::sleep_for(std::chrono::milliseconds(10));

        // 线程2：模拟ABA场景
        std::cout << "线程2开始制造ABA场景..." << std::endl;

        // 弹出几个元素
        auto a = aba_test_stack.pop();
        std::cout << "线程2弹出: " << *a << std::endl;

        auto b = aba_test_stack.pop();
        std::cout << "线程2弹出: " << *b << std::endl;

        // 删除节点（模拟内存回收）
        // 注意：在实际中，这里可能被内存分配器重用

        // 重新push（可能重用相同内存地址）
        aba_test_stack.push(999);
        std::cout << "线程2压入: 999" << std::endl;

        std::cout << "ABA场景制造完成" << std::endl;
        });

    t1.join();
    t2.join();

    std::cout << "测试完成，栈是否为空: " << (aba_test_stack.empty() ? "是" : "否") << std::endl;
}

// 性能测试
void performance_test() {
    LockFreeStack<int> stack;
    const int num_operations = 100000;

    auto start = std::chrono::high_resolution_clock::now();

    // 单线程性能测试
    for (int i = 0; i < num_operations; ++i) {
        stack.push(i);
    }
    for (int i = 0; i < num_operations; ++i) {
        stack.pop();
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    std::cout << "ABA安全栈 " << num_operations << " 次操作耗时: "
        << duration.count() << " ms" << std::endl;
}

int main() {
    test_aba_safe_stack();
    performance_test();
    return 0;
}


















